If the postorder and inorder traversal sequences of a binary tree are the same, then none of the nodes in the tree has a right child. (2分)
is . (2分)
If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then sequential storage works the fastest. (2分)
Given the input sequence onto a stack as {1, 2, 3, ..., }. If the first output is , then the -th output must be . (2分)
The best "worst-case time complexity" for any algorithm that sorts by comparisons only must be . (2分)
For a binary search tree, in which order of traversal that we can obtain a non-decreasing sequence? (3分)
Which one of the following relations is correct about the extra space taken by heap sort, quick sort and merge sort? (3分)
Given the pushing sequence of a stack as {1, 2, 3, 4, 5}. If the first number being popped out is 4, then the last one out must be: (3分)
Insert {5, 2, 7, 3, 4, 1, 6} one by one into an initially empty min-heap. The preorder traversal sequence of the resulting tree is: (6分)
Given a tree of degree 4. Suppose that the numbers of nodes of degrees 2, 3 and 4 are 4, 2 and 1, respectively. Then the number of leaf nodes must be: (6分)
Suppose that the height of a binary tree is (the height of a leaf node is defined to be 1), and it has only the nodes of degrees 0 and 2. Then the minimum and maximum possible total numbers of nodes are: (6分)
Suppose that an array of size m
is used to store a circular queue. If the front position is front
and the current size is size
, then the rear element must be at: (6分)
Suppose that the level-order traversal sequence of a min-heap is {1, 3, 2, 5, 4, 7, 6}. Use the linear algorithm to adjust this min-heap into a max-heap. The inorder traversal sequence of the resulting tree is: (6分)
Among the following sorting methods, which one may cause that none of the elements are at their final positions before the last run begins? Assume that there are more than 2 elements to be sorted. (3分)
To delete p
from a doubly linked list, we must do: (6分)
Given input { 321, 156, 57, 46, 28, 7, 331, 33, 34, 63 }. Which one of the following is the result after the 1st run of the Least Signification Digit (LSD) radix sort? (4分)
The array representation of a disjoint set containing numbers 0 to 8 is given by { 1, -4, 1, 1, -3, 4, 4, 8, -2 }. Then to union the two sets which contain 6 and 8 (with union-by-size), the index of the resulting root and the value stored at the root are: (6分)
If on the 9th level of a complete binary tree (assume that the root is on the 1st level) there are 100 leaf nodes, then the maximum number of nodes of this tree must be: (6分)
The function is to lower the value of the integer key at position P
by a positive amount D
in a min-heap H
.
void DecreaseKey( int P, int D, PriorityQueue H )
{
int i, key;
key = H->Elements[P] - D;
for ( i = (3分); H->Elements[i/2] > key; i/=2 )
(3分);
H->Elements[i] = key;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案正确 | 3 |
You are supposed to output, in decreasing order, all the elements no less than X
in a binary search tree T
.
void Print_NLT( Tree T, int X );
where Tree
is defined as the following:
typedef struct TreeNode *Tree;
struct TreeNode {
int Element;
Tree Left;
Tree Right;
};
The function is supposed to use Output(X)
to print X
.
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode *Tree;
struct TreeNode {
int Element;
Tree Left;
Tree Right;
};
Tree BuildTree(); /* details omitted */
void Output( int X ); /* details omitted */
void Print_NLT( Tree T, int X );
int main()
{
Tree T;
int X;
T = BuildTree();
scanf("%d", &X);
Print_NLT( T, X );
printf("End\n");
return 0;
}
/* Your function will be put here */
92 91 90 85 81 80 End
End
int a[1000] = {0}, st = -1; int cmp(const void *l, const void *r) { return *(int*)r-*(int*)l; } void Tr(Tree T, int X) { if (T) { if (T->Element >= X) { a[++st] = T->Element; } Tr(T->Left, X); Tr(T->Right, X); } } void Print_NLT( Tree T, int X ) { Tr(T, X); qsort(a, st+1, sizeof(int), cmp); for (int i = 0; i<=st; i++) { Output(a[i]); } }
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 7 | 2 ms | 256 KB |
1 | 答案正确 | 3 | 2 ms | 256 KB |
2 | 答案正确 | 6 | 2 ms | 296 KB |
3 | 答案正确 | 2 | 2 ms | 256 KB |
4 | 答案正确 | 2 | 3 ms | 256 KB |
a.c: In function ‘BuildTree’: a.c:33:6: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^~~~~~~~~~~~~~~ a.c:35:10: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &x); ^~~~~~~~~~~~~~~ a.c: In function ‘main’: a.c:52:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &X); ^~~~~~~~~~~~~~~